package class03;

import utils.ArrayUtil;

import java.util.Arrays;

/**
 * @Description: 有序递增数组找 <= value 的最右侧位置
 * @Author: WangWenpeng Sprint
 * @Date: 17:53 2021/6/15
 * @Version 1.0
 */
public class Code03_BSNearRight {

    /**
     * 二分法 有序递增数组中查找 <= value的最右侧位置
     */
    public static int nearRightIndex(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] <= value) {
                index = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return index;
    }

    /**
     * 循环求解
     */
    public static int violenceForSearch(int arr[], int value) {
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] <= value) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 测试方法
     *
     * @param args
     */
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;

        for (int i = 0; i < testTime; i++) {
            int[] arr = ArrayUtil.generateRandomArray(maxSize, maxValue, true, false);
            Arrays.sort(arr);

            int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            if (violenceForSearch(arr, value) != nearRightIndex(arr, value)) {
                ArrayUtil.printArray(arr);
                System.out.println(value);
                System.out.println(violenceForSearch(arr, value));
                System.out.println(nearRightIndex(arr, value));
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }
}
